package algorithm.easy;

import javafx.scene.transform.Rotate;
import pojo.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: LevelOrder32II  剑指 Offer 32 - II. 从上到下打印二叉树 II
 * @description: 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
 *
 *
 *
 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * 返回其层次遍历结果：
 *
 * [
 *   [3],
 *   [9,20],
 *   [15,7]
 * ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/2316:41
 * @since V1.0
 */
public class LevelOrder32II {
    //二叉树 队列

    /**
     * 算法流程：
     *
     *     特例处理： 当根节点为空，则返回空列表 [] ；
     *     初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] ；
     *     BFS 循环： 当队列 queue 为空时跳出；
     *         新建一个临时列表 tmp ，用于存储当前层打印结果；
     *         当前层打印循环： 循环次数为当前层节点数（即队列 queue 长度）；
     *             出队： 队首元素出队，记为 node；
     *             打印： 将 node.val 添加至 tmp 尾部；
     *             添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
     *         将当前层结果 tmp 添加入 res 。
     *     返回值： 返回打印结果列表 res 即可。
     *
     * 作者：jyd
     * 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root==null){
            ArrayList<List<Integer>> objects = new ArrayList<>();
            return objects;
        }
        Deque<TreeNode> que = new LinkedList<>();
        ArrayList<Integer> temp = null;
        List<List<Integer>> res = new ArrayList<>();
        que.addLast(root);
        while (!que.isEmpty()){
            temp = new ArrayList<>();
            int size = que.size();
            for(int i=0;i<size;i++ ){
                TreeNode node = que.pollFirst();
                temp.add(node.val);
                if (node.left!=null){
                    que.addLast(node.left);
                }
                if (node.right!=null){
                    que.addLast(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }
}
